The invention relates to data compression and more particularly to compression of a continuous flow of multidimensional data in real-time using vector quantization.
The next generation of satellite-based remote sensing instruments will produce an unprecedented volume of data. Imaging spectrometers, also known as hyper-spectral imaging devices, are prime examples. They collect image data in hundreds of spectral bands simultaneously from the near ultraviolet to the short wave infrared, and are capable of providing direct identification of surface materials.
Hyper-spectral data thus collected are typically in the form of a three-dimensional (3D) data cube. Each data cube has two dimensions in the spatial domain defining a rectangular plane of image pixels, and a third dimension in the spectral domain defining radiance levels of multiple spectral bands per each image pixel. The volume and complexity of hyper-spectral data present a significant challenge to conventional transmission and image analysis methods.
Data compression using Vector Quantisation (VQ) has received much attention because of its promise of high compression ratio and relatively simple structure. The VQ procedure is known to have two main steps: codebook generation and codevector matching. VQ can be viewed as mapping a large set of vectors into a small cluster of indexed codevectors forming a codebook. During encoding, a search through a codebook is performed to find a best codevector to express each input vector. The index or address of the selected codevector in the codebook is stored associated with the input vector or the input vector location. Given two systems having a same codebook, transmission of the index to a decoder over a communication channel from the first system to the second other system allows a decoder within the second other system to retrieve the same codevector from an identical codebook. This is a reconstructed approximation of the corresponding input vector. Compression is thus obtained by transmitting the index of the codevector rather the codevector itself.
In an article entitled xe2x80x9cLossy Compression of Hyperspectral Data Using Vector Quantizationxe2x80x9d by Michael Ryan and John Arnold in the journal Remote Sens. Environ., Elsevier Science Inc., New York, N.Y., 1997, Vol. 61, pp. 419-436, an overview of known general vector quantization techniques is presented. The article is herein incorporated by reference. In particular, the authors describe issues such as distortion measures and classification issues arising from lossy compression of hyper-spectral data using vector quantization.
However, implementation of a lossy compression method such as the VQ for real-time data compression of a continuous data flow is substantially complicated due to the fact that the complete hyper-spectral data cube is not available for compression. In real-time compression onboard a satellite, hyper-spectral data corresponding to only a 2D focal plane frame sensed at a given moment from a swath targetxe2x80x94across track linexe2x80x94on ground is available together with the hyper-spectral data corresponding to 2D focal plane frames sensed before. Onexe2x80x94spatialxe2x80x94dimension of the 2D focal plane frame corresponds to a line of ground samplesxe2x80x94called ground pixels, and another dimension of the 2D focal plane frame corresponds to a spectrum expansion of each ground pixel in wavelength. The spectrum expansion of a ground pixel is referred to as a xe2x80x9cspectral vector.xe2x80x9d A focal plane frame comprises a same number of spectral vectors and ground pixels. The second spatial dimension of the hyper-spectral data cube is obtained by sensing successive swath targets in along-track direction of the moving satellite producing successive 2D focal plane frames.
Therefore, it is only possible to apply the compression to successive 2D plane frames or successive regions comprising several 2D plane frames substantially inhibiting successful application of lossy compression such as VQ at high compression ratios with excellent fidelity. Furthermore, application of conventional lossy compression methods on datacubes representative of regions results in visible artifacts at the boundaries between different regions when the data is uncompressed and severely affects image quality after decompression.
It is, therefore, an object of the present invention to provide a method for compression of a continuous data flow based on a lossy compression method.
It is further an object of the present invention to provide a method for pipeline compression of a continuous data flow having a high compression ratio and without image artifacts.
It is yet another object of the present invention to provide a system for data compression of a continuous data flow.
In data compression, a series of 2D data subsets acquired in a given period of time are treated as a regional data cube for the purpose of dividing a continuous series of 2D data subsets into a plurality of data cubes. Reuse of existing codevectors is important in achieving high compression performance. For encoding spectral vectors on a subset-by-subset basis in a current region, two types of codevectors are used: codevectors that have been newly trained for data subsets in the current region and codevectors trained for the previous region. The problem of a visible spatial boundary between two adjacent regions after decompression is overcome by reusing the codevectors trained from a previous region to encode the spectral vectors in the current region in order to attain a seamless conjunction of the two adjacent regions. Experimental results show that the method for compressing a continuous data flow according to the present invention performs as well as data compression performed in batch mode. Therefore, the method is highly advantageous in, for example, space applications or medical imaging.
In accordance with the invention there is provided, a method for compression of a continuous data flow comprising the steps of:
a) receiving a nth data subset of the continuous data flow, the nth data subset comprising a plurality of data vectors indicative of a nth portion of an image of an object;
b) selecting for each data vector of the nth data subset a codevector from a nxe2x88x921th codebook that approximates the respective data vector, the nxe2x88x921th codebook comprising codevectors for encoding at least a portion of the data vectors of the nxe2x88x921th data subset;
c) determining a fidelity for the approximation of each data vector of the nth data subset;
d) when the fidelity for the approximation of a data vector of the nth data subset is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;
e) repeating the steps a) to d) for encoding data vectors of subsequent data subsets;
f) collecting un-encoded data vectors;
g) determining at least a codevector through training for approximating the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;
i) storing the at least a trained codevector in the respective codebook; and,
j) encoding the un-encoded data vectors based on the at least a trained codevector.
In accordance with the invention there is further provided, a method for compression of a continuous data flow comprising the steps of:
a) receiving a nth data subset of a mth region of the continuous data flow, the nth data subset comprising a plurality of data vectors indicative of a nth portion of the mth region of an image of an object;
b) selecting for each data vector of the nth data subset of the mth region a codevector from a mth regional codebook that approximates the respective data vector, the mth regional codebook comprising codevectors for encoding at least a portion of the data vectors of at least a data subset of the first to the nxe2x88x921th data subsets of the mth region;
c) determining a fidelity for the approximation of each data vector of the nth data subset of the mth region;
d) when the fidelity for the approximation of a data vector of the nth data subset of the mth region is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;
e) when the fidelity for the approximation of a data vector of the nth data subset of the mth region is below the predetermined threshold performing the step of selecting a second codevector from the mxe2x88x921th regional codebook that approximates the data vector;
f) determining a fidelity for the second approximation of the data vector;
g) when the fidelity for the second approximation of the data vector is above the predetermined threshold performing the step of encoding the data vector based on the selected second codevector;
h) repeating the steps a) to g) for encoding data vectors of subsequent data subsets within the mth region;
i) collecting un-encoded data vectors of subsequent data subsets;
j) determining at least a codevector through training for approximating each of the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;
k) storing the at least a trained codevector in the mth regional codebook;
l) encoding the un-encoded data vectors based on the at least a trained codevector;
m) storing in the mth regional index map at least an index indicative of the at least a trained codevector""s location within the mth regional codebook; and,
n) providing the mth regional codebook and the mth regional index map for transmission.
In accordance with an aspect of the invention there is provided, a storage medium having stored thereon at least an executable command for when executed resulting in performance of the steps of:
a) receiving a nth data subset of a mth region of the continuous data flow, the nth data subset comprising a plurality of data vectors indicative of a nth portion of the mth region of an image of an object;
b) selecting for each data vector of the nth data subset of the mth region a codevector from a mth regional codebook that approximates the respective data vector, the mth regional codebook comprising codevectors for encoding at least a portion of the data vectors of the first to the nxe2x88x921th data subsets of the mth region;
c) determining a fidelity for the approximation of each data vector of the nth data subset of the mth region;
d) when the fidelity for the approximation of a data vector of the nth data subset of the mth region is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;
e) when the fidelity for the approximation of a data vector of the nth data subset of the mth region is below the predetermined threshold performing the step of selecting a second codevector from the mxe2x88x921th regional codebook that approximates the data vector;
f) determining a fidelity for the second approximation of the data vector;
g) when the fidelity for the second approximation of the data vector is above the predetermined threshold performing the step of encoding the data vector based on the selected second codevector;
h) repeating the steps a) to g) for encoding data vectors of subsequent data subsets within the mth region;
i) collecting un-encoded data vectors of subsequent data subsets;
j) determining at least a codevector through training for approximating each of the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;
k) storing the at least a trained codevector in the mth regional codebook; and,
l) encoding the un-encoded data vectors based on the at least a trained codevector;
n) providing the mth regional codebook and the mth regional index map for transmission; and, repeating the steps h) to n) for subsequent regions.
In accordance with an aspect of the invention there is provided, a system for compressing a continuous data flow comprising: a first port for receiving the continuous data flow; electronic circuitry in data communication with the first port, the electronic circuitry for performing the steps of:
a) receiving a nth data subset of a mth region of the continuous data flow, the nth data subset comprising a plurality of data vectors indicative of a nth portion of the mth region of an image of an object;
b) selecting for each data vector of the nth data subset of the mth region a codevector from a mth regional codebook that approximates the respective data vector, the mth regional codebook comprising codevectors for encoding at least a portion of the data vectors of the first to the nxe2x88x921th data subsets of the mth region;
c) determining a fidelity for the approximation of each data vector of the nth data subset of the mth region;
d) when the fidelity for the approximation of a data vector of the nth data subset of the mth region is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;
e) when the fidelity for the approximation of a data vector of the nth data subset of the mth region is below the predetermined threshold performing the step of selecting a second codevector from the mxe2x88x921th regional codebook that approximates the data vector;
f) determining a fidelity for the second approximation of the data vector;
g) when the fidelity for the second approximation of the data vector is above the predetermined threshold performing the step of encoding the data vector based on the selected second codevector;
h) repeating the steps a) to g) for encoding data vectors of subsequent data subsets within the mth region;
i) collecting un-encoded data vectors of subsequent data subsets;
j) determining at least a codevector through training for approximating each of the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;
k) storing the at least a trained codevector in the mth regional codebook;
l) encoding the un-encoded data vectors based on the at least a trained codevector;
n) providing the mth regional codebook and the mth regional index map for transmission; and, repeating the steps h) to n) for subsequent regions; and, a second port in data communication with the electronic circuitry for providing the regional codebook and the regional index map.
In accordance with the aspect of the invention there is further provided, a storage medium having stored thereon at least an executable command for when executed resulting in performance of the steps of:
a) receiving a nth data subset of the continuous data flow, the nth data subset comprising a plurality of data vectors indicative of a nth portion of an image of an object;
b) selecting for each data vector of the nth data subset a codevector from a nxe2x88x921th codebook that approximates the respective data vector, the nxe2x88x921th codebook comprising codevectors for encoding at least a portion of the data vectors of the nxe2x88x921th data subset;
c) determining a fidelity for the approximation of each data vector of the nth data subset;
d) when the fidelity for the approximation of a data vector of the nth data subset is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;
e) repeating the steps a) to d) for encoding data vectors of subsequent data subsets;
f) collecting un-encoded data vectors;
g) determining at least a codevector through training for approximating each of the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;
i) storing the at least a trained codevector in the respective codebook;
j) encoding the un-encoded data vectors based on the at least a trained codevector; and, storing in an index map an index indicative of a codevector""s location within the respective codebook.
In accordance with the aspect of the invention there is further provided, a system for compressing a continuous data flow comprising: a first port for receiving the continuous data flow; electronic circuitry in data communication with the first port, the electronic circuitry for performing the steps of:
a) receiving a nth data subset of the continuous data flow, the nth data subset comprising a plurality of data vectors indicative of a nth portion of an image of an object;
b) selecting for each data vector of the nth data subset a codevector from a nxe2x88x921th codebook that approximates the respective data vector, the nxe2x88x921th codebook comprising codevectors for encoding at least a portion of the data vectors of the nxe2x88x921th data subset;
c) determining a fidelity for the approximation of each data vector of the nth data subset;
d) when the fidelity for the approximation of a data vector of the nth data subset is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;
e) repeating the steps a) to d) for encoding data vectors of subsequent data subsets;
f) collecting un-encoded data vectors;
g) determining at least a codevector through training for approximating each of the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;
i) storing the at least a trained codevector in the respective codebook;
j) encoding the un-encoded data vectors based on the at least a trained codevector; and, storing in an index map an index indicative of a codevector""s location within the respective codebook; and,
a second port in data communication with the electronic circuitry for providing the codebook and the index map.